/**
 * 198. 打家劫舍
 */
public class Solution_198 {
    /**
     * 动态规划经典例题
     * 
     * 最简单的情况：
     *   如果只有一间房屋，则偷窃该房屋，可以偷窃到最高总金额。
     *   如果只有两间房屋，则由于两间房屋相邻，不能同时偷窃，只能偷窃其中的一间房屋，
     *     因此选择其中金额较高的房屋进行偷窃，可以偷窃到最高总金额。
     * 
     * 如果房屋的数量大于2，那么对于第 k(k>2) 间房屋，有两个选项：
     *   1. 偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，
     *      偷窃总金额为前 k-2 间房屋的最高总金额与第 k 间房屋的金额之和。
     *   2. 不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
     * 在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
     * 
     * 用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
     *          dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
     * 边界条件：
     *          dp[0] = nums[0]       只有一间房屋，则偷窃该房屋
     *          dp[1] = max(nums[0], nums[1])       只有两间房屋，选择金额较高的房屋偷窃
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }

        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[len - 1];
    }

    public static void main(String[] args) {
        Solution_198 solution = new Solution_198();
        int[] nums = { 2, 7, 9, 3, 1 };
        int ans = solution.rob(nums);
        System.out.println(ans);
    }
}
